package leetcode_bin_tree_test;

import bin_tree.TreeNode;

import java.util.*;

/**
 * 二叉搜索树中的众数
 */
public class FindMode {
    static List<Integer> answer = new ArrayList<>();
    static int base, count, maxCount;

    public static int[] findMode(TreeNode root) {
        if (root.left == null && root.right == null) {
            return new int[] {root.val};
        }
        inOrder(root);
        update(100001);
        int[] ret = new int[answer.size()];
        for (int i = 0; i < answer.size(); i++) {
            ret[i] = answer.get(i);
        }
        return ret;
    }

    private static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        update(root.val);
        inOrder(root.right);
    }

    private static void update(int val) {
        if (base == val) {
            count ++;
        } else {
            if (count == maxCount) {
                answer.add(base);
            } else if (count > maxCount) {
                answer.clear();
                answer.add(base);
                maxCount = count;
            }
            base = val;
            count = 1;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(2);
        TreeNode n4 = new TreeNode(3);
        TreeNode n5 = new TreeNode(3);
        TreeNode n6 = new TreeNode(3);
        root.right = n1;
        n1.left = n2;
        n1.right = n4;
        n2.left = n3;
        n4.left = n5;
        n4.right = n6;
        System.out.println(Arrays.toString(findMode(root)));
    }
}
